package leetcode_ago.LinearList.double_link;

public class DoubleLinkedList {
    private int size;
    private Node head;
    private Node tail;
    /**
     * 4.删
     */
    public void removeIndex(int index){//删除索引位置对应节点
        if(rangeIndex(index)){
            Node node=node(index);
            //删除某个节点
            delete(node);
        }else{
            System.out.println("remove index illegal");
            return;
        }
    }
    public void removeFirst(){
        removeIndex(0);
    }
    public void removeLast(){
        removeIndex(size-1);
    }

    /**
     * 删除具体某个节点
     * 思路：分治,先处理左边判断是否prev空，再看右边判断是否next空
     * @param node
     */
    private void delete(Node node) {
        Node prev=node.prev;//待删除结点的前一位
        Node next=node.next;//待删除结点的后一位
        if(prev==null){
            //待删除结点是头节点
            head=next;
        }else{
            //待删除结点不是头节点
            prev.next=next;
            node.prev=null;
        }
        if(next==null){
            //待删除结点是尾节点
            tail=prev;
        }else{
            next.prev=prev;
            node.next=null;
        }
        size--;
    }
    public void removeValOnce(int val){//删除某个值对应节点
        //找到待删除节点，再进行删除操作
        for(Node node=head;node!=null;node=node.next){
            if(node.val==val){
                delete(node);
                break;
            }
        }
    }
    public void removeValAll(int val){//删除所有值为val对应的节点
        for(Node node=head;node!=null;){
            if(node.val==val){
                //暂存下一节点的地址
                Node temp=node.next;
                delete(node);
                //把下一节点的地址更新给node
                node=temp;
            }else{
                node=node.next;

            }
        }
    }
    /**
     * 3.改
     * 根据索引修改索引位置元素值为newVal,返回未修改之前index位置的元素值
     */
    public int set(int index,int newVal){
        if(rangeIndex(index)){
            Node cur=node(index);
            int oldVal=cur.val;
            cur.val=newVal;
            return oldVal;
        }else {
            System.out.println("set index illegal");
            return -1;
        }
    }
    /**
     * 2.查找
     */
    public boolean contains(int val){//元素是否存在
        for(Node x=head;x!=null;x=x.next){
            if(x.val==val){
                return true;
            }
        }
        return false;
    }
    public int get(int index){//index位置节点对应的元素值，返回元素值
        //判断index的合法性，也可以抽象成一个方法
        if(rangeIndex(index)){
            Node cur=node(index);
            return cur.val;
        }else {
            System.out.println("get index illegal");
            return -1;
        }
    }

    private boolean rangeIndex(int index) {
        if(index<0||index>=size){
            return false;
        }
        return true;
    }

    /**
     * 1.向链表中插入元素
     */
    public void addFirst(int val){//头插
        Node node=new Node(null,val,head);
        if(head==null){
            tail=node;
            head=node;
        }else{
            head.prev=node;
            head=node;
        }
        size++;
    }
    public void addLast(int val){//尾插
        Node node=new Node(tail,val,null);
        if(tail==null){
            head=node;
            tail=node;
        }else{
            tail.next=node;
            tail=node;
        }
        size++;
    }
    public void indexAdd(int index,int val){//中间插入
        if(index<0||index>size){
            System.out.println("add index illegal");
            return;
        }else if(index==0){
            addFirst(val);
        }else if(index==size){
            addLast(val);
        }else{
            //找到index位置的前驱节点
            //根据索引找节点CURD都能用，可以抽象成一个方法
            Node prev=node(index-1);
            Node node=new Node(prev,val,prev.next);//这一步把newNode.prev=prev和newNode.next=prev.next都走了
            prev.next.prev=node;
            prev.next=node;
            size++;
        }
    }

    /**
     * 找index位置对应节点
     * @param index
     * @return
     */
    private Node node(int index) {
        Node cur=null;
        if(index<(size>>1)){
           cur=head;
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
        }else{
            cur=tail;
            for (int i = size-1; i >index ; i--) {
                cur=cur.prev;
            }
        }
        return cur;
    }

    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder("");
        Node node=head;
        while(node!=null){
            sb.append(node.val);
            sb.append("->");
            node=node.next;
        }
        sb.append("NULL");
        String ret=sb.toString();
        return ret;
    }
}
class Node{
    //前驱节点
    Node prev;
    //保存具体值
    int val;
    //指向后继节点
    Node next;
    public Node(Node prev, int val, Node next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}